package 二分;
/**
    @author: TTDB
    @create: 2025/9/20
*/
public class searchInsert {
    public int searchInsert(int[] nums, int target) {
        return left_bound(nums, target);
    }

    // 搜索左侧边界的二分算法
    int left_bound(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        // 注意
        int right = nums.length;

        // 注意
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                //==right
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                // 注意
                right = mid;
            }
        }
        return left;
    }

    //标准的
    public boolean search(int[] nums, int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                return true;
            }
        }
        return false;
    }

    //right边界
    public int searchright(int[] nums, int target){
        int left = 0, right = nums.length;
        while(left < right){//left = right退出
            int mid = left + (right-left)/2;
            if(nums[mid] < target){
                //左收缩右边界
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return right - 1;
    }
}
